package com.g01.by;

import com.g01.qt.Node;

import java.util.Stack;

public class PalindromesSeq {
    public static void main(String[] args) {
        // 测试用例
        int[] a = {1, 2, 2, 1};
        Node al = Node.createLinkNode(a);
        int[] b = {1, 2, 3, 4};
        Node bl = Node.createLinkNode(b);
        System.out.println(JudgePalindromesSeq.useStack(al));
        System.out.println(JudgePalindromesSeq.useStack(bl));
        System.out.println(JudgePalindromesSeq.useDoubleP(al));
        System.out.println(JudgePalindromesSeq.useDoubleP(bl));
    }
}

class JudgePalindromesSeq {
    // 用栈
    static Boolean useStack(Node head) {
        Stack<Node> stack = new Stack<>();
        // 全部入栈
        Node temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.getNext();
        }
        // 反向遍历比较
        while (!stack.isEmpty()) {
            if (head.getData() == stack.pop().getData()) {
                head = head.getNext();
            } else {
                return false;
            }
        }
        return true;
    }

    // 用双指针
    static Boolean useDoubleP(Node head) {
        Stack<Node> st = new Stack<>();
        Node slow = head;
        Node quick = head;
        while (quick != null  && quick.getNext() != null) {  // 慢走一步，快走两步
            st.push(slow);
            slow = slow.getNext();
            quick = quick.getNext().getNext();
        }
        while (!st.isEmpty()) {
            if (st.pop().getData() == slow.getData()) {
                slow = slow.getNext();
            } else {
                return false;
            }
        }
        return true;
    }
}
